package org.example.Backtracking_algorithm;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Combination_Total_III {
    public static List<List<Integer>> result = new ArrayList<>();
    public static LinkedList<Integer> value = new LinkedList<>();
    public static void main(String[] args) {
        //组合总和 III

        //找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
        //只使用数字1到9
        //每个数字 最多使用一次
        //返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
        int k = 9;
        int n = 45;
        combinationSum3(k,n);
        prin();
    }
    public static List<List<Integer>> combinationSum3(int k, int n) {
        get(k,n,1,0);
        return result;
    }
    public static void  get(int k,int n,int index,int sum){
        if (value.size()==k && sum==n){
            result.add(new ArrayList<>(value));
            return;
        }
        for (int i = index; i <= 9; i++) {
            sum+=i;
            value.add(i);
            get(k,n,i+1,sum);
            value.removeLast();
            sum-=i;
        }
    }
    public static void prin(){
        for (List<Integer> list : result) {
            System.out.print("[ ");
            for (Integer integer : list) {
                System.out.print(integer);
            }
            System.out.print(" ]");
        }
        System.out.println();
    }
}
